package com.jwetherell.my.sort;

public class SortingProblemsAndSolutions {

	
	/**
	 * Problem: Find the Minimum length Unsorted Subarray, sorting which makes the complete array sorted
	 * 
	 * http://www.geeksforgeeks.org/minimum-length-unsorted-subarray-sorting-which-makes-the-complete-array-sorted/
	 * 
	 * Time Complexity: O(n)
	 */
	public static void findMinLengthUsortedSubArray(int [] data) {
		
		int startIndex = -1;
		for (int i = 0; i < (data.length - 1); i++) {
			if (data[i] > data[i+1]) {
				startIndex = i;
				break;
			}
		}
		
		if (startIndex == -1) // data already sorted
			return;
	
		int endIndex = -1;
		for (int i = (data.length - 1); i >= 1; i--) {
			if (data[i-1] > data[i]) {
				endIndex = i;
				break;
			}
		}
		
		int min = data[startIndex];
		int max = data[startIndex];
		for (int i = startIndex + 1; i <= endIndex; i++) {
			if (data[i] < min)
				min = data[i];
			if (data[i] > max)
				max = data[i];
		}
		
		/**
		 * Note: Here we are finding a startIndex (if any) which is less than the
		 * current startIndex
		 */
		for (int i = 0; i < startIndex; i++) {
			if (data[i] > min) {
				startIndex = i;
				break;
			}
		}
		
		for (int i = (data.length - 1); i > endIndex; i--) {
			if (data[i] < max) {
				endIndex = i;
				break;
			}
		}
		
		System.out.println("StartIndex: " + startIndex);
		System.out.println("EndIndex: " + endIndex);
		
	}
	
	public static void main(String[] args) {
//		int [] data = new int[] {10, 12, 20, 30, 25, 40, 32, 31, 35, 50, 60};
		int [] data = new int[] {0, 1, 15, 25, 6, 7, 30, 40, 50};
		
		findMinLengthUsortedSubArray(data);
	}
}
